package list;

public class MyTreeSet<T> {
    private Node root;
    private static class Node<T>{
        T value;
        Node left;
        Node right;
        public Node(T e){
            value = e;
        }
        /*
         * 中序遍历算法
         */
        public void appendTo(StringBuilder builder){
            if(left != null){
                left.appendTo(builder);
            }
            System.out.println("添加:"+value);
            builder.append(value).append(", ");
            if (right != null){
                right.appendTo(builder);
            }
        }

        /*
         * add Child 添加孩子，
         */
        public boolean addChild(T e){
            //先比较大小，如果小了就加到 左侧， 如果大了就加到右侧
            Comparable obj = (Comparable)e;
            int result = obj.compareTo(value);
            if (result==0){ //数据不允许重复，重复就返回false，表示添加失败
                return false;
            }else if(result<0){//e 小于 value，向左侧添加
                if (left==null) {
                    left = new Node(e);
                    System.out.println("添加："+value+"的左侧"+e);
                    return true;
                }else {
                    return left.addChild(e);
                }
            }else { //e 大于 value，向右侧添加
                if (right==null) {
                    right = new Node(e);
                    System.out.println("添加："+value+"的右侧"+e);
                    return true;
                }else {
                    return right.addChild(e);
                }
            }
        }
    }
    public boolean add(T e){
        //先检查对象是否能够进行大小比较
        if(! (e instanceof Comparable)){
            throw new RuntimeException("无比较大小方法："+e);
        }
        if(root == null){
            root = new Node(e);
            System.out.println("添加跟元素："+e);
            return true;
        }else {
            //先和根元素的数据比较大小，如果小就放到右侧
            //Comparable val = (Comparable)e; //转换类型以后就为了调用比较大小方法
            // obj1.compareTo(obj2) 如果返回0 就表示两个对象相等
            // 如果是正数表示obj1大， 如果返回负数obj1小
            //int result = val.compareTo(root.value);
            return root.addChild(e);
        }

    }

    @Override
    public String toString() {
        if (root==null){
            return "[]";
        }
        StringBuilder builder = new StringBuilder("[");
        //将根元素添加到 StringBuilder
        root.appendTo(builder);
        builder.delete(builder.length()-2, builder.length());
        return builder.append(']').toString();
    }
}
